package com.algorithm.dp;

import static com.google.common.primitives.Ints.max;

public class LongestCommonSequence {
    public static void main(String[] args) {
        String seq1 = "ABCDEFGHIJKLMN";
        String seq2 = "ADCFBGNKJHDHGK";
        int l = calc(seq1, seq2);
        int n = calcLCS(seq1, seq2);
        System.out.println(l);
        System.out.println(n);
    }

    /**
     * 递推方式实现
     *
     * @param str1
     * @param str2
     * @return
     */
    private static int calcLCS(String str1, String str2) {
        Integer[][] dp = new Integer[str1.length()][str2.length()];

        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[0].length; j++) {
                String left1 = str1.substring(0, i + 1);
                String left2 = str2.substring(0, j + 1);
                if (left1.length() == 0 || left2.length() == 0) {
                    dp[i][j] = 0;
                } else if (left1.length() == 1) {
                    dp[i][j] = left2.contains(left1) ? 1 : 0;
                } else if (left2.length() == 1) {
                    dp[i][j] = left1.contains(left2) ? 1 : 0;
                } else {
                    String end1 = left1.substring(left1.length() - 1);
                    String end2 = left2.substring(left2.length() - 1);
                    if (end1.equals(end2)) {
                        dp[i][j] = dp[i - 1][j - 1] + 1;
                    } else {
                        dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                    }
                }
            }
        }
        return dp[dp.length - 1][dp[0].length - 1];
    }

    /**
     * 递归方式实现,缺点:重复计算量太大
     *
     * @param str1
     * @param str2
     * @return
     */
    public static final int calc(String str1, String str2) {
        if (str1.length() == 0) {
            return 0;
        }
        if (str2.length() == 0) {
            return 0;
        }
        if (str1.length() == 1) {
            return str2.contains(str1) ? 1 : 0;
        }
        if (str2.length() == 1) {
            return str1.contains(str2) ? 1 : 0;
        }
        String end1 = str1.substring(str1.length() - 1);
        String end2 = str2.substring(str2.length() - 1);
        String left1 = str1.substring(0, str1.length() - 1);
        String left2 = str2.substring(0, str2.length() - 1);

        if (end1.equals(end2)) {
            return calc(left1, left2) + 1;
        } else {
            return max(calc(str1, left2), calc(str2, left1));
        }

    }
}
